package leetcode.weekly.week307;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

//Solution4Test
public class Solution5 {

	public long kSum(int[] nums, int k) {
		Integer[] numss = new Integer[nums.length];
		for (int i = 0; i < numss.length; i++) {
			numss[i] = nums[i];
		}
		Arrays.sort(numss, (a, b) -> b.compareTo(a));
		PriorityQueue<Long> queue = new PriorityQueue<>((a, b) -> a.compareTo(b));
//		queue.add(0l);
		int i = 0;
		for (; i < nums.length && queue.size() < k; i++) {
			long num = numss[i];
			List<Long> list = new ArrayList<>();
			list.add(num);
			while (!queue.isEmpty()) {
				long cur = queue.poll();
				list.add(cur + num);
				list.add(cur);
			}
			queue.addAll(list);
		}
		queue.add(0l);
		long sum = 0;
		for (; i < numss.length; i++) {
			if (numss[i] > 0) {
				sum += 1l * numss[i];
			}
		}
		while (queue.size() > k) {
			queue.poll();
		}
		System.out.println(queue.peek());
		return sum + queue.peek();
	}

}
